package com.peng.leetcode.heap;


import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * MergeKLists
 * <p>
 * 23. 合并K个升序链表
 *
 * @author: lupeng6
 * @create: 2021/2/4 16:58
 */
public class MergeKLists {

    public static void main(String[] args) {

    }


    public ListNode mergeKLists(ListNode[] lists) {
        ListNode dump = new ListNode(-1);
        ListNode curr = dump;
        PriorityQueue<ListNode> minHeap = new PriorityQueue<>(Comparator.comparingInt(n -> n.val));
        for (ListNode node : lists) {
            minHeap.offer(node);
        }
        while (!minHeap.isEmpty()) {
            ListNode listNode = minHeap.poll();
            curr.next = listNode;
            if (listNode.next != null) {
                minHeap.offer(listNode.next);
            }
            curr = curr.next;
        }
        return dump.next;
    }


    static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
}
